Three-dimensional models of input objects may be digitally modeled (e.g. on a computer system and/or other suitable processor(s)) in volumetric representations known as tetrahedral-meshes or “tet-meshes”. There are techniques known in the art for obtaining tet-mesh representations of objects. For example, isotropic volumetric tet-meshes can be generated from isotropic surface meshes using known software, such as Tetgen™. Non-isotropic surface meshes can be re-meshed using known software such as Graphite™ and the re-meshed surface meshes may then be used to generate suitable volumetric tet-meshes.
Due to their numerical properties, volumetric hexahedral-meshes (“hex-meshes”) of objects may be preferred volumetric representations (over tet-meshes) for a variety of applications. Non-limiting examples of applications where hex-meshes are preferred over tet-meshes include numerical simulations used in engineering applications. However, automatically generating volumetric hex-meshes from the tet-meshes of arbitrary input objects where the hex-meshes exhibit suitably high quality (e.g. element shape quality and connectivity) remains an open problem. Consequently, industrial practitioners still largely rely on a variety of semi-manual hex-meshing approaches which require considerable user interaction, and can involve days or even weeks to generate hex-meshes of complex shapes.
One known approach for all-hexahedral (or “all-hex”) meshing, referred to as mapping or sub-mapping, is based on a volumetric mapping between the input model of an object (typically, but not necessarily, modeled as a tetrahedral-mesh typically referred to as a “tet-mesh”) and a so-called “polycube” representation of the input object. A polycube is a solid formed by joining several cubes face-to-face. A polycube has a trivial hex mesh. Sub-mapping methods relate the trivial hex-mesh of the polycube to the input object model using the volumetric mapping to provide an output hex-mesh corresponding to the input object. Typically, these methods require that the polycube representation of the input object and the mapping between the input object model and the polycube representation be generated manually by the user or with significant user input. For these sub-mapping techniques, the quality of the output hex-mesh depends significantly on distortion associated with the mapping between the input object model and the polycube. There is accordingly a general desire to provide methods for automatically generating low-distortion mappings between input objects (e.g. having general shapes) and corresponding polycube representations.
There is a general desire to generate hex-meshes having reasonable quality in terms of quality metrics referred to as element shape quality and connectivity. Element shape quality is often defined as the deviation of hex-mesh elements from a perfect cube. When a hex-mesh is used for particular applications (e.g. engineering simulations and/or the like), the element shape quality of the hex-mesh can impact the accuracy and/or robustness of simulations. Simulation results depend not only on average element shape quality, but also on minimum element shape quality with even a single “inverted” (negative Jacobian) element rendering a hex-mesh unusable for simulation. Connectivity of a hex-mesh representation also impacts the ability to use the hex-mesh for particular applications. For example, when a hex-mesh is used for engineering simulations, connectivity of the hex-mesh can impact hex-mesh processing time, the ability to use distributed processing (parallelization) to implement the simulation and/or the like.
Known hex-meshing techniques used in industry tend to fall into two categories: hex-dominant and grid-based. Hex-dominant methods tend to create meshes which include a significant percentage of non-hex elements (e.g. often more than 20%). When using the resulting mesh for subsequent applications (e.g. engineering simulations and/or the like), non-hex elements require specialized numerics and may not suit some applications. Grid-based methods (also known as octree methods) intersect the input model with a Cartesian grid defining the mesh interior. This grid is then connected to the surface using a variety of techniques. Grid-based methods often need excessively fine local element sizes on off-axis or concave features and tend to form low shape quality elements with irregular connectivity in regions corresponding to such features.
There is a general desire to provide techniques to generate hex-mesh volumetric representations of objects which overcome or ameliorate some of the issues with prior art techniques.
The foregoing examples of the related art and limitations related thereto are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those of skill in the art upon a reading of the specification and a study of the drawings.